package com.demo.链表.chenglei;

import cn.hutool.core.lang.Console;

import java.util.*;

/**
 * 链表相交问题
 * @author cl
 */
public class Linked02 {

    public static void main(String[] args) {
        // 案例链表（无）： 5 -> 8 -> 4 -> 1 -> 2 -> 0 -> 3 -> 9
        Integer[] test0 = new Integer[]{5, 8, 4, 1, 2, 0, 3, 9};
        Linked.LinkedNode<Integer> head0 = Linked.makeSingleLinked(test0, true);
        // 案例链表（有）： 5 -> 8 -> 4 -> 1 -> （2 -> 0 -> 3 -> 9）
        Linked.LinkedNode<Integer> head1 = Linked.makeSingleLinked(test0, true);
        Linked.LinkedNode<Integer> circleNode = Linked.getLinkedNode(head1, 2).get(0);
        Linked.LinkedNode tailNode = head1;
        while (tailNode.next != null && (tailNode = tailNode.next) != null){}
        tailNode.next = circleNode;
        Linked.LinkedNode<Integer> t = getCircleNodeBySet(head0);
        Console.log("getCircleNodeBySet： head0 链表是否有环: {}, 环点是: {}", t != null, t!= null ? t.data : null);
        t = getCircleNodeByPoint(head0);
        Console.log("getCircleNodeByPoint： head0 链表是否有环: {}, 环点是: {}", t != null, t!= null ? t.data : null);
        Linked.LinkedNode<Integer> t1 = getCircleNodeBySet(head1);
        Console.log("getCircleNodeBySet： head1 链表是否有环: {}, 环点是: {}", t1 != null, t1 != null ? t1.data : null);
        t1 = getCircleNodeByPoint(head1);
        Console.log("getCircleNodeByPoint： head1 链表是否有环: {}, 环点是: {}", t1 != null, t1 != null ? t1.data : null);
        Console.log("*********");
        两无环链表相交();
        Console.log("*********");
        两有环链表不相交();
        Console.log("*********");
        两有环链表相交1();
        Console.log("*********");
        两有环链表相交2();
    }

    public static void 两无环链表相交() {
        // 做成相交链表 相交部分 6 7 8 9 10 相交位置为 6
        Integer[] test0 = new Integer[]{11, 22, 33, 44, 15, 6, 7, 8, 9, 10};
        Integer[] test1 = new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        HashMap<Integer, Linked.LinkedNode<Integer>> map = new HashMap<>();
        for(Integer t : test0) {
            map.putIfAbsent(t, new Linked.LinkedNode<>(t));
        }
        for(Integer t : test1) {
            map.putIfAbsent(t, new Linked.LinkedNode<>(t));
        }
        Linked.LinkedNode<Integer> head1 = null;
        Linked.LinkedNode<Integer> tail1 = null;
        for(Integer t : test0) {
            if (head1 == null) {
                head1 = map.get(t);
                tail1 = map.get(t);
            } else {
                tail1.next = map.get(t);
                tail1 = tail1.next;
            }
        }
        Linked.LinkedNode<Integer> head2 = null;
        Linked.LinkedNode<Integer> tail2 = null;
        for(Integer t : test1) {
            if (head2 == null) {
                head2 = map.get(t);
                tail2 = map.get(t);
            } else {
                tail2.next = map.get(t);
                tail2 = tail2.next;
            }
        }
        两链表相交(head1, head2);
    }

    public static void 两有环链表不相交() {
        // 做成两个有环链表
        // 案例链表（有）： 1 -> 2 -> 3 -> （4 -> 5 -> 6 -> 7 -> 8）
        Integer[] test1 = new Integer[] {1, 2, 3, 4, 5, 6, 7, 8};
        List<Linked.LinkedNode<Integer>> circleLinked1 =  Linked.createCircleLinked(test1, 4);
        // 案例链表（有）： 11 -> 12 -> 13 -> （14 -> 15 -> 16 -> 17 -> 18）
        Integer[] test2 = new Integer[] {11, 12, 13, 14, 15, 16, 17, 18};
        List<Linked.LinkedNode<Integer>> circleLinked2 =  Linked.createCircleLinked(test2, 14);
        两链表相交(circleLinked1.get(0), circleLinked2.get(0));
    }

    public static void 两有环链表相交1() {
        // 情况2 第一种
        // 做成两个有环链表
        // 案例链表（有）： 1 -> 2 -> 3 -> （4 -> 5 -> 6 -> 7 -> 8）
        // 案例链表（有）： 11 -> 12 -> 13 -> 14 ->（4 -> 5 -> 6 -> 7 -> 8）
        // 相交点4
        Console.log(">>> 情况2 1");
        Integer[] test1 = new Integer[] {1, 2, 3, 4, 5, 6, 7, 8};
        Integer[] test2 = new Integer[] {11, 12, 13, 14, 4, 5, 6, 7, 8};
        List<Linked.LinkedNode<Integer>> list = 相交链表做成(test1, test2, 4, 4);
        两链表相交(list.get(0), list.get(1));
        // 情况2 第二种
        // 做成两个有环链表
        // 案例链表（有）： 1 -> 2 -> 3 -> （4 -> 5 -> 6 -> 7 -> 8）
        // 案例链表（有）： 11 -> 12 -> 13 -> 14 ->3 -> （4 -> 5 -> 6 -> 7 -> 8）
        // 相交点3
        Console.log(">>> 情况2 2");
        Integer[] test3 = new Integer[] {1, 2, 3, 4, 5, 6, 7, 8};
        Integer[] test4 = new Integer[] {11, 12, 13, 14, 3, 4, 5, 6, 7, 8};
        List<Linked.LinkedNode<Integer>> list1 = 相交链表做成(test3, test4, 4, 4);
        两链表相交(list1.get(0), list1.get(1));
    }

    public static void 两有环链表相交2() {
        // 情况3
        // 做成两个有环链表
        // 案例链表（有）： 1 -> 2 -> 3 -> （4 -> 5 -> 6 -> 7 -> 8）
        // 案例链表（有）： 11 -> 12 -> 13 -> （7 ->8 -> 4 -> 5 -> 6）
        // 相交点4
        Console.log(">>> 情况2 1");
        Integer[] test1 = new Integer[] {1, 2, 3, 4, 5, 6, 7, 8};
        Integer[] test2 = new Integer[] {11, 12, 13, 7, 8, 4, 5, 6};
        List<Linked.LinkedNode<Integer>> list = 相交链表做成(test1, test2, 4, 7);
        两链表相交(list.get(0), list.get(1));
    }

    private static List<Linked.LinkedNode<Integer>> 相交链表做成(Integer[] linked1, Integer[] linked2, Integer c1, Integer c2) {
        HashMap<Integer, Linked.LinkedNode<Integer>> map = new HashMap<>();
        for(Integer t : linked1) {
            map.putIfAbsent(t, new Linked.LinkedNode<>(t));
        }
        for(Integer t : linked2) {
            map.putIfAbsent(t, new Linked.LinkedNode<>(t));
        }
        Linked.LinkedNode<Integer> head1 = null;
        Linked.LinkedNode<Integer> tail1 = null;
        for(Integer t : linked1) {
            if (head1 == null) {
                head1 = map.get(t);
                tail1 = map.get(t);
            } else {
                tail1.next = map.get(t);
                tail1 = tail1.next;
            }
        }
        tail1.next = map.get(c1);
        Linked.LinkedNode<Integer> head2 = null;
        Linked.LinkedNode<Integer> tail2 = null;
        for(Integer t : linked2) {
            if (head2 == null) {
                head2 = map.get(t);
                tail2 = map.get(t);
            } else {
                tail2.next = map.get(t);
                tail2 = tail2.next;
            }
        }
        tail2.next = map.get(c2);
        Linked.LinkedNode<Integer> finalHead = head1;
        Linked.LinkedNode<Integer> finalHead1 = head2;
        return new ArrayList<Linked.LinkedNode<Integer>>(){{add(finalHead); add(finalHead1);}};
    }

    public static <T> void 两链表相交(Linked.LinkedNode<T> head1, Linked.LinkedNode<T> head2) {
        Objects.requireNonNull(head1);
        Objects.requireNonNull(head2);
        // 判断是否有环
        Linked.LinkedNode<T> l1 = getCircleNodeByPoint(head1);
        Linked.LinkedNode<T> l2 = getCircleNodeByPoint(head2);
        if (l1 == null && l2 == null) {
            // 两个无环链表
            Console.log("链表1：{}", Linked.printSingleLinkedToString(head1));
            Console.log("链表2：{}", Linked.printSingleLinkedToString(head2));
            Console.log("此为两个无环链表相交判断");
            两个无环链表相交(head1, head2);
        } else if (l1 != null && l2 != null) {
            Console.log("环链表1：{}", Linked.printSingleLinkedToString(head1, l1));
            Console.log("还链表2：{}", Linked.printSingleLinkedToString(head2, l2));
            Console.log("此为两个有环链表相交判断");
            两个有环链表相交(head1, head2, l1, l2);
        } else {
            Console.log("一个有环，一个无环，不会相交的");
        }
    }

    private static <T> void 两个无环链表相交(Linked.LinkedNode<T> head1, Linked.LinkedNode<T> head2) {
        Objects.requireNonNull(head1);
        Objects.requireNonNull(head2);
        int l1Size = 1;
        int l2Size = 1;
        Linked.LinkedNode<T> l1Tail = head1;
        Linked.LinkedNode<T> l2Tail = head2;
        while (l1Tail.next != null) {
            l1Size++;
            l1Tail = l1Tail.next;
        }
        while (l2Tail.next != null) {
            l2Size++;
            l2Tail = l2Tail.next;
        }
        if (l1Tail != l2Tail) {
            Console.log("两个链表不相交");
            return;
        }
        // 相交
        int cha = 0;
        if ((cha = l1Size - l2Size) > 0) {
            // l1 长
            while (cha-- > 0) {
                head1 = head1.next;
            }
        } else {
            // l2 长
            cha = -1 * cha;
            while (cha-- > 0) {
                head2 = head2.next;
            }
        }
        while (head1.next != null) {
            head1 = head1.next;
            head2 = head2.next;
            if (head1 == head2) {
                Console.log("两个链表相交， 相交位置为: {}", head1.data);
                break;
            }
        }
    }

    private static <T> void 两个有环链表相交(Linked.LinkedNode<T> head1, Linked.LinkedNode<T> head2, Linked.LinkedNode<T> circle1, Linked.LinkedNode<T> circle2) {
        Objects.requireNonNull(head1);
        Objects.requireNonNull(head2);
        Objects.requireNonNull(circle1);
        Objects.requireNonNull(circle2);
        if (circle1 == circle2) {
            // 情况2： 两个有环链表相交，但只有一个交点，那么它们必定共用环，所以环点一定是同一个节点。
            // 将环点作为尾节点 那么就是两个无环链表的相交问题了
            circle1.next = null;
            两个无环链表相交(head1, head2);
        } else {
            // 从任意一个环点开始遍历，环中若存在另一个环点 则是 情况3 否则 情况1
            Linked.LinkedNode<T> tmp = circle1.next;
            while (tmp != circle1) {
                tmp = tmp.next;
                // 情况3： 两个有环链表相交，有两个交点，那么它们也是共用环，不过环点不是同一个节点即链表1的环点是链表2的环的一点，反之亦然，且两个环点即是交点。
                if (tmp == circle2) {
                    Console.log("两个链表相交， 相交位置为: {}, {}", circle1.data, circle2.data);
                    return;
                }
            }
            // 情况1： 两个有环链表不相交，即两个环点都不会出现在另一个链表上。
            Console.log("两个链表不相交");
        }
    }

    public static <T> Linked.LinkedNode<T> getCircleNodeBySet(Linked.LinkedNode<T> head) {
        Objects.requireNonNull(head);
        Set<Linked.LinkedNode<T>> tmpSet = new HashSet<>();
        while (head != null) {
            if (tmpSet.contains(head)) {
                return head;
            } else {
                tmpSet.add(head);
            }
            head = head.next;
        }
        return null;
    }

    public static <T> Linked.LinkedNode<T> getCircleNodeByPoint(Linked.LinkedNode<T> head) {
        Objects.requireNonNull(head);
        Linked.LinkedNode<T> slowPoint = head;
        Linked.LinkedNode<T> quickPoint = head;
        Linked.LinkedNode<T> firstMeet = null;
        // 慢指针一次走一步 快指针走两步
        while (slowPoint.next != null && quickPoint.next != null && quickPoint.next.next != null) {
            slowPoint = slowPoint.next;
            quickPoint = quickPoint.next.next;
            // 是否相遇
            if (slowPoint == quickPoint) {
                firstMeet = slowPoint;
                break;
            }
        }
        // 不相遇
        if (firstMeet == null) {
            return firstMeet;
        }
        // 第一次相遇 快指针回到头结点
        quickPoint = head;
        // 都一次走一步
        while (quickPoint.next != null) {
            quickPoint = quickPoint.next;
            slowPoint = slowPoint.next;
            if (quickPoint == slowPoint) {
                return quickPoint;
            }
        }
        throw new RuntimeException("这里是逻辑有问题吧?");
    }
}
